package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.util.InputParseUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q_合并区间 {

    public static void main(String[] args) {
        List list = InputParseUtil.parse("[[1,3],[2,6],[8,10],[15,18]]");
        int[][] input = InputParseUtil.listToArray2Int(list);
        Q_合并区间 exe = new Q_合并区间();
        int[][] res = exe.merge(input);
        for (int[] re : res) {
            Tools.printArray(re);
        }
    }

    /*
    * 思想实验, 按 start, end, length 排序的效果
    * */

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 按 start 升序
                return o1[0] - o2[0];
            }
        });

        int i = 0;
        int n = intervals.length;
        int cnt = 0;
        while (++i < n) {
            if (intervals[i][0] <= intervals[i-1][1]) {
                intervals[i] = new int[]{intervals[i-1][0], Math.max(intervals[i-1][1], intervals[i][1])};
                intervals[i-1] = null;
                cnt++;
            }
        }

        int[][] ans = new int[n - cnt][];
        int j = 0;
        for (int[] interval : intervals) {
            if (interval != null) {
                ans[j++] = interval;
            }
        }

        return ans;
    }


}
